0833. 字符串中的查找与替换【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 模拟

1. 📝 题目描述

• leetcode

你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出：indices, sources, targets。

要完成第 i 个替换操作:

1. 检查 子字符串 sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。
2. 如果没有出现， 什么也不做。
3. 如果出现，则用 targets[i] 替换 该子字符串。

例如，如果 s = "abcd"， indices[i] = 0 , sources[i] = "ab"， targets[i] = "eee"，那么替换的结果将是 "eeecd"。

所有替换操作必须 同时 发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠。

• 例如，一个 s = "abc"， indices = [0,1]， sources = ["ab"，"bc"] 的测试用例将不会生成，因为 "ab" 和 "bc" 替换重叠。

在对 s 执行所有替换操作后返回 结果字符串。

子字符串 是字符串中连续的字符序列。

---

示例 1：

输入：s = "abcd", indices = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
输出："eeebffff"
解释：
"a" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
"cd" 从 s 中的索引 2 开始，所以它被替换为 "ffff"。

示例 2：

输入：s = "abcd", indices = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
输出："eeecd"
解释：
"ab" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
"ec" 没有从原始的 S 中的索引 2 开始，所以它没有被替换。

---

提示：

• 1 <= s.length <= 1000
• k == indices.length == sources.length == targets.length
• 1 <= k <= 100
• 0 <= indices[i] < s.length
• 1 <= sources[i].length, targets[i].length <= 50
• s 仅由小写英文字母组成
• sources[i] 和 targets[i] 仅由小写英文字母组成

2. 🎯 s.1 - 模拟

c

char* findReplaceString(char* s, int* indices, int indicesSize, char** sources, int sourcesSize, char** targets, int targetsSize) {
    int order[indicesSize];
    for (int i = 0; i < indicesSize; i++) order[i] = i;
    for (int i = 0; i < indicesSize; i++)
        for (int j = i + 1; j < indicesSize; j++)
            if (indices[order[i]] < indices[order[j]]) { int t = order[i]; order[i] = order[j]; order[j] = t; }
    char* res = (char*)malloc(strlen(s) * 10 + 1000);
    strcpy(res, s);
    for (int k = 0; k < indicesSize; k++) {
        int i = order[k], idx = indices[i];
        int srcLen = strlen(sources[i]);
        if (strncmp(res + idx, sources[i], srcLen) == 0) {
            int tgtLen = strlen(targets[i]);
            int resLen = strlen(res);
            memmove(res + idx + tgtLen, res + idx + srcLen, resLen - idx - srcLen + 1);
            memcpy(res + idx, targets[i], tgtLen);
        }
    }
    return res;
}

js

/**
 * @param {string} s
 * @param {number[]} indices
 * @param {string[]} sources
 * @param {string[]} targets
 * @return {string}
 */
var findReplaceString = function (s, indices, sources, targets) {
  const ops = indices.map((idx, i) => [idx, sources[i], targets[i]])
  ops.sort((a, b) => b[0] - a[0])
  let res = s
  for (const [idx, src, tgt] of ops) {
    if (res.slice(idx, idx + src.length) === src)
      res = res.slice(0, idx) + tgt + res.slice(idx + src.length)
  }
  return res
}

py

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        ops = sorted(zip(indices, sources, targets), reverse=True)
        res = list(s)
        for idx, src, tgt in ops:
            if s[idx:idx + len(src)] == src:
                res[idx:idx + len(src)] = list(tgt)
        return ''.join(res)

• 时间复杂度：$O(n+k\log k)$，其中 n 是字符串长度，k 是替换操作数
• 空间复杂度：$O(n)$

算法思路：

• 将替换操作按索引降序排列，从后往前替换避免索引偏移
• 每次检查对应位置是否匹配 source，匹配则替换为 target